package com.zlk.algorithm.algorithm.dynamicPlan.knapsack073;

import javafx.scene.chart.Axis;
import org.junit.Test;

// 最后一块石头的重量 II
// 有一堆石头，用整数数组 stones 表示
// 其中 stones[i] 表示第 i 块石头的重量。
// 每一回合，从中选出任意两块石头，然后将它们一起粉碎
// 假设石头的重量分别为 x 和 y，且 x <= y
// 那么粉碎的可能结果如下：
// 如果 x == y，那么两块石头都会被完全粉碎；
// 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x
// 最后，最多只会剩下一块 石头，返回此石头 最小的可能重量
// 如果没有石头剩下，就返回 0
// 测试链接 : https://leetcode.cn/problems/last-stone-weight-ii/
public class Code04_LastStoneWeightII {


    @Test
    public void test(){
        int[] arr = new int[]{57,32,40,27,35,61};
        System.out.println(lastStoneWeightII(arr));
    }

    public int lastStoneWeightII(int[] stones) {
        if(stones.length==0){
            return -1;
        }
        if(stones.length==1){
            return  stones[0];
        }
        if(stones.length==2){
            return  Math.abs(stones[0]-stones[1]);
        }
        int n = stones.length;
        int sum = 0;
        for (int i = 0; i < stones.length; i++) {
            sum+=stones[i];
        }
        int m = sum/2;
        //0 到i位置，选取得累加和等于j是否有效
        // dp[i][j] = dp[i-1][j]||dp[]
        boolean[]dp = new boolean[m+1];//此处是m不是sum 仔细一点
        //不要0位置
        dp[0]=true;
        //要0位置
        if(stones[0]!=0&&stones[0]<=m){
            dp[stones[0]]=true;
        }
        for (int i = 1,cur; i < n; i++) {
            cur = stones[i];
            for (int j = m; j >=cur ; j--) {//注意是j-- 不要写太快检查一下
                dp[j] = dp[j]||dp[j-cur];
            }
        }
        for (int i = dp.length-1; i >= 0; i--) {
            if(dp[i]){
                return sum-i-i;
            }
        }
        return -1;

    }


    public  int lastStoneWeightII2(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        // nums中随意选择数字
        // 累加和一定要 <= sum / 2
        // 又尽量接近
        //本质就是找出一个集合无限趋近中间值
        int near = near(nums, sum / 2);
        return sum - near - near;
    }

    //背包找出 小于等于sum的最大值
    //dp含义 0到i位置找出小于等于j的最大累加和
    // dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i])
    // ans = dp[n][sum]
    private  int near(int[] nums, int sum) {
        int[] dp = new int[sum+1];
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            for (int j = sum; j >=num; j--) {
                dp[j] =Math.max(dp[j],dp[j-num]+num);
            }
        }
        return dp[sum];
    }

}
